//给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 
//
// 示例: 
//
// 输入: [0,1,0,3,12]
//输出: [1,3,12,0,0] 
//
// 说明: 
//
// 
// 必须在原数组上操作，不能拷贝额外的数组。 
// 尽量减少操作次数。 
// 
// Related Topics 数组 双指针 
// 👍 728 👎 0

package leetcode.editor.cn;

//Java：移动零
public class P283MoveZeroes {

    /**
     *
     * 思路：双指针，左指针为第一次出现0的位置，然后右指针往右遍历，遇到不是0的，为左指针交换
     *
     * 执行用时： 0 ms , 在所有 Java 提交中击败了 100.00% 的用户 内存消耗： 40.1 MB , 在所有 Java 提交中击败了 44.90% 的用户
     *
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public void moveZeroes(int[] nums) {
            int left = 0;

            // 找到第一次为0的位置
            while (left < nums.length && nums[left] != 0) {
                left++;
            }

            // 1 2 3 0 4 5 6 7 0 9 8 4 1
            int right = left + 1;
            for (; right < nums.length; right++) {
                if (nums[right] != 0) {
                    swap(nums, left, right);
                    left++;
                }
            }
        }

        private void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        int[] nums = new int[]{0,1,0,3,12};
        Solution solution = new P283MoveZeroes().new Solution();
        solution.moveZeroes(nums);
        System.out.println(nums);
        // TO TEST
    }

}